import java.util.Vector;

public class Jigsaw {
    jigsawNode beginJNode;	  // 拼图的起始状态节点
    jigsawNode endJNode;	  // 拼图的目标状态节点
    jigsawNode currentJNode;  // 拼图的当前状态节点
    private final Vector<jigsawNode> openList;	  // open表：用以保存已发现但未访问的节点
    private final Vector<jigsawNode> closeList;	  // close表：用以保存已访问的节点
    private Vector<jigsawNode> solutionPath;  // 解路径：用以保存从起始状态到达目标状态的移动路径中的每一个状态节点
    private boolean isCompleted;	          // 完成标记：初始为false;当求解成功时，将该标记置为true
    private int searchedNodesNum;	          // 已访问节点数： 用以记录所有访问过的节点的数量

    public Jigsaw(jigsawNode bNode, jigsawNode eNode) {
        this.beginJNode = new jigsawNode(bNode);
        this.endJNode = new jigsawNode(eNode);
        this.currentJNode = new jigsawNode(bNode);
        this.openList = new Vector<>();
        this.closeList = new Vector<>();
        this.solutionPath = null;
        this.isCompleted = false;
        this.searchedNodesNum = 0;
    }

    /**
     * @param jNode -> 初始状态节点
     * @param len -> 随机移动的步数
     */
    public static jigsawNode scatter(jigsawNode jNode, int len) {
        int randomDirection;
        len += (int) (Math.random() * 2);
        jigsawNode jigsawnode = new jigsawNode(jNode);
        for (int i = 0; i < len; i++) {
            int[] movable = jigsawnode.canMove();
            do {
                randomDirection = (int) (Math.random() * 4);
            }
            while(movable[randomDirection] == 0);
            jigsawnode.move(randomDirection);
        }
        jigsawnode.init();
        return jigsawnode;
    }

    public jigsawNode getCurrentJNode() {
        return currentJNode;
    }

    public jigsawNode getBeginJNode() {
        return beginJNode;
    }

    public jigsawNode getEndJNode() {
        return endJNode;
    }

    public boolean isCompleted() {
        return isCompleted;
    }

    /**
     *
     */
    private void calSolutionPath() {
        if (this.isCompleted()) {
            jigsawNode jNode = this.currentJNode;
            solutionPath = new Vector<>();
            while (jNode != null) {
                solutionPath.addElement(jNode);
                jNode = jNode.getParent();
            }
        }
    }

    /**
     * @return 解路径solutionPath的字符串
     */
    public String getSolutionPath() {
        StringBuilder str = new StringBuilder();
        str.append("Begin->");
        if (this.isCompleted) {
            for (int i = solutionPath.size()-1; i>=0; i--) {
                str.append(solutionPath.elementAt(i).toString()).append("->");
                str.append("\n");
            }
            str.append("End");
        } else
            str = new StringBuilder("Jigsaw Not Completed.");
        return str.toString();
    }

    public int getSearchedNodesNum() {
        return searchedNodesNum;
    }

    public void printResult() {
        if (this.isCompleted) {
            // 输出到控制台
            System.out.println("Jigsaw Completed");
            System.out.println("Begin state:" + this.getBeginJNode().toString());
            System.out.println("End state:" + this.getEndJNode().toString());
            System.out.println("Solution Path: ");
            System.out.println(this.getSolutionPath());
            System.out.println("Total number of searched nodes:" + this.getSearchedNodesNum());
            System.out.println("Length of the solution path is:" + this.getCurrentJNode().getNodeDepth());

        } else {
            // 输出到控制台
            System.out.println("No solution. Jigsaw Not Completed");
            System.out.println("Begin state:" + this.getBeginJNode().toString());
            System.out.println("End state:" + this.getEndJNode().toString());
            System.out.println("Total number of searched nodes:" + this.getSearchedNodesNum());
        }
    }

    /**
     * 探索所有与jNode邻接且未曾被访问的节点
     * @param jNode -> 要探索的节点
     * @return 包含所有与jNode邻接且未曾被访问的节点的Vector<JigsawNode>对象
     */
    private Vector<jigsawNode> findFollowJNodes(jigsawNode jNode) {
        Vector<jigsawNode> followJNodes = new Vector<>();
        jigsawNode tempJNode;
        for(int i=0; i<4; i++){
            tempJNode = new jigsawNode(jNode);
            if(tempJNode.move(i) && !this.closeList.contains(tempJNode) && !this.openList.contains(tempJNode))
                followJNodes.addElement(tempJNode);
        }
        return followJNodes;
    }

    /**
     * 排序插入openList：按照节点的代价估值（estimatedValue）将节点插入openList中，估值小的靠前
     */
    private void sortedInsertOpenList(jigsawNode jNode) {
        this.estimateValue(jNode);
        for (int i = 0; i < this.openList.size(); i++) {
            if (jNode.getEstimatedValue() < this.openList.elementAt(i)
                    .getEstimatedValue()) {
                this.openList.insertElementAt(jNode, i);
                return;
            }
        }
        this.openList.addElement(jNode);
    }

    public void ASearch() {
        // 访问节点数大于30000个则认为搜索失败0s
        int maxNodesNum = 25000;

        // 用以存放某一节点的邻接节点
        Vector<jigsawNode> followJNodes;

        // 重置求解完成标记为false
        isCompleted = false;

        // (1)将起始节点放入openList中
        this.sortedInsertOpenList(this.beginJNode);

        // (2) 如果openList为空，或者访问节点数大于maxNodesNum个，则搜索失败，问题无解;否则循环直到求解成功
        while (!this.openList.isEmpty() && searchedNodesNum <= maxNodesNum) {

            // (2-1)访问openList的第一个节点N，置为当前节点currentJNode
            //      若currentJNode为目标节点，则搜索成功，设置完成标记isCompleted为true，计算解路径，退出。
            this.currentJNode = this.openList.elementAt(0);
            if (this.currentJNode.equals(this.endJNode)){
                isCompleted = true;
                this.calSolutionPath();
                break;
            }

            // (2-2)从openList中删除节点N,并将其放入closeList中，表示以访问节点
            this.openList.removeElementAt(0);
            this.closeList.addElement(this.currentJNode);
            searchedNodesNum++;

            // (2-3)寻找所有与currentJNode邻接且未曾被访问的节点，将它们按代价估值从小到大排序插入openList中
            followJNodes = this.findFollowJNodes(this.currentJNode);
            while (!followJNodes.isEmpty()) {
                this.sortedInsertOpenList(followJNodes.elementAt(0));
                followJNodes.removeElementAt(0);
            }
        }
        this.printResult();
    }

    /**
     * 计算并修改状态节点jNode的代价估计值:f(n)=s(n),s(n)代表后续节点不正确的数码个数
     * @param jNode -> 要计算代价估计值的节点
     */
    private void estimateValue(jigsawNode jNode) {
        int f1 = 0;  // 后续节点不正确的数码个数
        int f2 = 0;  //所有放错位的数码个数
        int f3 = 0;  //所有放错位的数码与其正确位置的距离之和 曼哈顿距离
        int f4 = 0;  //几何距离
        int dimension = jigsawNode.getDimension();
        for(int index = 1 ; index < dimension*dimension; index++){
            if(jNode.getNodesState()[index]+1!=jNode.getNodesState()[index+1])
                f1++;
            if (jNode.getNodesState()[index] != index && jNode.getNodesState()[0] != index) {
                f2++;
                int x1 = (index-1) / dimension;
                int y1 = (index-1) % dimension;
                int x2 = (jNode.getNodesState()[index]-1) / dimension;
                int y2 = (jNode.getNodesState()[index]-1) % dimension;
                f3 += Math.abs(x1-x2) + Math.abs(y1-y2);
                f4 += Math.sqrt(Math.abs(x1-x2)) + Math.sqrt(Math.abs(y1-y2));
            }
        }
        jNode.setEstimatedValue(2*f1 + 3*f2 + 7*f3 + f4);
    }
}